package top.minuy.structure.graph.matching;

import top.minuy.structure.graph.bipartition.dfs.BipartitionDetection;
import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;

/**
 * 匈牙利最大匹配算法，广度优先遍历
 * O(V*E)
 *
 * @author Minuy
 * @time 7:55
 * @date 2021/11/30
 */
public class Hungarian {

    private Graph g; // 图
    private int[] matching; // 匹配数组
    private int maxMatching; // 最大匹配值

    public Hungarian(Graph g) {
        this.g = g;

        if (g.isDirected()) {
            throw new IllegalArgumentException("BipartiteMatching only works in undirected graph.");
        }

        BipartitionDetection bd = new BipartitionDetection(g);
        if (!bd.isBipartition()) {
            throw new IllegalArgumentException("BipartiteMatching only works for bipartite graph.");
        }

        maxMatching = 0;
        matching = new int[g.V()];
        for (int i = 0; i < matching.length; i++) {
            matching[i] = -1;
        }

        for (int v = 0; v < g.V(); v++) {
            // 没有匹配，并且是这边的
            if (matching[v] == -1 && bd.isBlue(v)) {
                if (bfs(v)) {
                    maxMatching++;
                }
            }
        }
    }

    /**
     * 广度优先遍历匹配算法
     *
     * @param s 源点
     * @return boolean 是否匹配成功
     * @author Minuy
     * @date 2021/11/30 8:23
     */
    private boolean bfs(int s) {
        ArrayList<Integer> queue = new ArrayList<>();

        int[] pre = new int[g.V()];
        for (int i = 0; i < matching.length; i++) {
            pre[i] = -1;
        }

        int v = s;
        queue.add(v);
        pre[v] = v;
        while (!queue.isEmpty()) {
            v = queue.remove(0);

            for (int w : g.adj(v)) {
                if (pre[w] == -1) {
                    pre[w] = v;
                    // 如果已经匹配过了，继续使用广度优先遍历
                    if (matching[w] != -1) {
                        // 绿色的可以直接跳过，即直接记录对其匹配的点
                        // queue.add(w);
                        queue.add(matching[w]);
                        // pre[w] = v; // 调整到if前面
                        pre[matching[w]] = w;
                    } else { // 找到没有匹配的了，获取路径，调整匹配项
                        // pre[w] = v; // 调整到if前面
                        ArrayList<Integer> path = getAugPath(pre, s, w);
                        // 重新设置匹配项
                        for (int i = 0; i < path.size(); i += 2) {
                            matching[path.get(i)] = path.get(i + 1);
                            matching[path.get(i + 1)] = path.get(i);
                        }
                        return true;
                    }
                }
            }
        }
        return false;
    }

    /**
     * 找出增广路径
     *
     * @param pre pre数组
     * @param s   源点
     * @param t   目标点
     * @return ArrayList<Integer> 增广路径
     * @author Minuy
     * @date 2021/11/30 8:20
     */
    private ArrayList<Integer> getAugPath(int[] pre, int s, int t) {
        ArrayList<Integer> path = new ArrayList<>();
        int cur = t;
        while (cur != s) {
            path.add(cur);
            cur = pre[cur];
        }
        path.add(s);
        return path;
    }

    /**
     * 获取最大匹配
     *
     * @return int 最大匹配
     * @author Minuy
     * @date 2021/11/29 21:37
     */
    public int maxMatching() {
        return maxMatching;
    }

    /**
     * 查看是否是完全匹配
     *
     * @return boolean 是否是完全匹配
     * @author Minuy
     * @date 2021/11/29 21:38
     */
    public boolean isPerfectMatching() {
        return maxMatching * 2 == g.V();
    }

    /**
     * 获取对应的匹配点
     *
     * @param v 顶点v
     * @return int 对应的顶点v的匹配点
     * @author Minuy
     * @date 2021/11/30 8:26
     */
    public int matching(int v) {
        g.validateVertex(v);
        return matching[v];
    }

}
